package leetcode.dynamic;

public class Lc53 {


    public static int maxSubArray(int[] nums) {

        int[] dp = new int[nums.length + 1];
        dp[0] = Integer.MIN_VALUE / 2;
        int ans = Integer.MIN_VALUE / 2;
        for (int i = 1; i <= nums.length; i++) {
            dp[i] = Math.max(dp[i-1] + nums[i-1], nums[i-1]);
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] n = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(maxSubArray(n));
    }
}
